package pers.qianyu.month_202012.date_20201202;

import java.util.*;
import java.util.stream.*;

/**
 * 1081. 不同字符的最小子序列
 * https://leetcode-cn.com/problems/smallest-subsequence-of-distinct-characters/
 *
 * @author mizzle rain
 * @date 2020-12-02 21:06
 */
public class SmallestSubsequence {
    public String smallestSubsequence(String s) {
        if (s == null || s.length() == 0) {
            return s;
        }
        int[] dict = new int[26];
        for (int i = 0; i < s.length(); i++) {
            dict[s.charAt(i) - 'a']++;
        }
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (!stack.contains(c)) {
                while (!stack.isEmpty() && stack.peek() > c && dict[stack.peek() - 'a'] > 0) {
                    stack.pop();
                }
                stack.push(c);
            }
            // 如果 stack 里面包含 c 直接跳过
            dict[s.charAt(i) - 'a']--;
        }
        return stack.stream().map(String::valueOf).collect(Collectors.joining(""));
    }

    public static void main(String[] args) {
        String param = "cdadabcc";
        System.out.println(Arrays.toString(param.toCharArray()));
        String result = new SmallestSubsequence().smallestSubsequence(param);
        System.out.println("result = " + result);
    }
}
